package com.lrs.java.dataStructure.linkList;

class DLink {
	public long dData; // data item
	public DLink next; // next DLink in list
	public DLink previous; // previous DLink in list
	// -------------------------------------------------------------

	public DLink(long d){
		dData = d;
	}

	// -------------------------------------------------------------
	public void displayDLink() {
		System.out.print(dData + " ");
	}
	// -------------------------------------------------------------
}

class DoublyDLinkedList {
	private DLink first; // ref to first item
	private DLink last; // ref to last item
	// -------------------------------------------------------------

	public DoublyDLinkedList() {
		first = null; // no items on list yet
		last = null;
	}

	// -------------------------------------------------------------
	public boolean isEmpty() {
		return first == null;
	}

	// -------------------------------------------------------------
	public void insertFirst(long dd) {
		DLink newDLink = new DLink(dd); // make new DLink

		if (isEmpty()) // if empty list,
			last = newDLink; // newDLink <-- last
		else
			first.previous = newDLink; // newDLink <-- old first
		newDLink.next = first; // newDLink --> old first
		first = newDLink; // first --> newDLink
	}

	// -------------------------------------------------------------
	public void insertLast(long dd) {
		DLink newDLink = new DLink(dd); // make new DLink
		if (isEmpty()) // if empty list,
			first = newDLink; // first --> newDLink
		else {
			last.next = newDLink; // old last --> newDLink
		}
		newDLink.previous = last; // old last <-- newDLink
		last = newDLink; // newDLink <-- last
	}

	// -------------------------------------------------------------
	public DLink deleteFirst() { // (assumes non-empty list)
		DLink temp = first;
		if (first.next == null) // if only one item
			last = null; // null <-- last
		else
			first.next.previous = null; // null <-- old next
		first = first.next; // first --> old next
		return temp;
	}

	// -------------------------------------------------------------
	public DLink deleteLast() { // (assumes non-empty list)
		DLink temp = last;
		if (first.next == null) // if only one item
			first = null; // first --> null
		else
			last.previous.next = null; // old previous --> null
		last = last.previous; // old previous <-- last
		return temp;
	}

	// -------------------------------------------------------------
	// insert dd just after key
	public boolean insertAfter(long key, long dd) { // (assumes non-empty list)
		DLink current = first; // start at beginning
		while (current.dData != key) // until match is found,
		{
			current = current.next; // move to next DLink
			if (current == null)
				return false; // didn't find it
		}
		DLink newDLink = new DLink(dd); // make new DLink

		if (current == last) // if last DLink,
		{
			newDLink.next = null; // newDLink --> null
			last = newDLink; // newDLink <-- last
		} else // not last DLink,
		{
			newDLink.next = current.next; // newDLink --> old next
											// newDLink <-- old next
			current.next.previous = newDLink;
		}
		newDLink.previous = current; // old current <-- newDLink
		current.next = newDLink; // old current --> newDLink
		return true; // found it, did insertion
	}

	// -------------------------------------------------------------
	public DLink deleteKey(long key) { // (assumes non-empty list)
		DLink current = first; // start at beginning
		while (current.dData != key) // until match is found,
		{
			current = current.next; // move to next DLink
			if (current == null)
				return null; // didn't find it
		}
		if (current == first) // found it; first item?
			first = current.next; // first --> old next
		else
			// not first
			// old previous --> old next
			current.previous.next = current.next;

		if (current == last) // last item?
			last = current.previous; // old previous <-- last
		else
			// not last
			// old previous <-- old next
			current.next.previous = current.previous;
		return current; // return value
	}

	// -------------------------------------------------------------
	public void displayForward() {
		System.out.print("List (first-->last): ");
		DLink current = first; // start at beginning
		while (current != null) // until end of list,
		{
			current.displayDLink(); // display data
			current = current.next; // move to next DLink
		}
		System.out.println("");
	}

	// -------------------------------------------------------------
	public void displayBackward() {
		System.out.print("List (last-->first): ");
		DLink current = last; // start at end
		while (current != null) // until start of list,
		{
			current.displayDLink(); // display data
			current = current.previous; // move to previous DLink
		}
		System.out.println("");
	}
	// -------------------------------------------------------------
} // end class DoublyDLinkedList
// //////////////////////////////////////////////////////////////

class DoublyDLinkedApp {
	public static void main(String[] args) { // make a new list
		DoublyDLinkedList theList = new DoublyDLinkedList();

		theList.insertFirst(22); // insert at front
		theList.insertFirst(44);
		theList.insertFirst(66);

		theList.insertLast(11); // insert at rear
		theList.insertLast(33);
		theList.insertLast(55);

		theList.displayForward(); // display list forward
		theList.displayBackward(); // display list backward

		theList.deleteFirst(); // delete first item
		theList.deleteLast(); // delete last item
		theList.deleteKey(11); // delete item with key 11

		theList.displayForward(); // display list forward

		theList.insertAfter(22, 77); // insert 77 after 22
		theList.insertAfter(33, 88); // insert 88 after 33

		theList.displayForward(); // display list forward
	} // end main()
}
